<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>egg drop</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
        
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        <style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="egg-drop">egg drop</h1>
<p><a href="https://leetcode.com/problems/super-egg-drop/">https://leetcode.com/problems/super-egg-drop/</a></p>
<pre><code><code><div>You are given K eggs, and you have access to a building with N floors from 1 to N. 
Each egg is identical in function, and if an egg breaks, you cannot drop it again.
You know that there exists a floor F with 0 &lt;= F &lt;= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.
Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 &lt;= X &lt;= N). 
Your goal is to know with certainty what the value of F is.
What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?
 
Example 1:
Input: K = 1, N = 2
Output: 2
Explanation: 
Drop the egg from floor 1.  If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2.  If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.
Example 2:
Input: K = 2, N = 6
Output: 3
Example 3:
Input: K = 3, N = 14
Output: 4
 
Note:
1 &lt;= K &lt;= 100
1 &lt;= N &lt;= 10000
</div></code></code></pre>
<h1 id="solutoion-1">solutoion 1</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=3hcaVyX00_4&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=13">https://www.youtube.com/watch?v=3hcaVyX00_4&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=13</a></li>
<li><a href="https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/gao-lou-reng-ji-dan-wen-ti">https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/gao-lou-reng-ji-dan-wen-ti</a></li>
</ul>
<p>这个问题涉及到3个变量.</p>
<ol>
<li>鸡蛋数目 K</li>
<li>大楼高度N</li>
<li>最多允许扔鸡蛋的数目D</li>
</ol>
<p>我们基于K和N构建矩阵, 矩阵元素是最多允许仍鸡蛋的数目D.  横坐标N,纵坐标K, 在求解Matrix(K,N)的时候， 我们第一次选择楼层k  (1&lt;= k &lt;= N)</p>
<ul>
<li>&lt;1&gt;如果鸡蛋破了, 那么还需要往下测试剩下的k-1层楼，  需要的测试次数是 1 + Matrix(K-1,k-1)</li>
<li>&lt;2&gt;如果鸡蛋没破， 那么还需要往上测试剩下的N-k层楼， 需要的测试测试是 1+ Matrix(K, N-k)</li>
</ul>
<p>如果F(K, N, k) 代表 K个鸡蛋， 楼高N， 第一次从第k层开始扔的情况下， 最后需要扔鸡蛋的数目</p>
<p>F(K,N,k) = max( 1 + Matrix(K-1,k-1),  1+ Matrix(K, N-k))</p>
<p>在所有可能k的情况下, Matrix(K,N) = min (F(K,N,k) |  1&lt;= k &lt;= N)</p>
<p>My solution 1(will timeout O(n^3):</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> pprint <span class="hljs-keyword">import</span> pprint
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
<span class="hljs-comment">#      0 1 2 3 4 5 ... N</span>
<span class="hljs-comment">#  0</span>
<span class="hljs-comment">#  1     1 2 3 4 5 ....N</span>
<span class="hljs-comment">#  2</span>
<span class="hljs-comment">#  .</span>
<span class="hljs-comment">#  K</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">superEggDrop</span><span class="hljs-params">(self, K: <span class="hljs-string">'int'</span>, N: <span class="hljs-string">'int'</span>)</span> -&gt; 'int':</span>
        matrix = [[<span class="hljs-number">0</span>]*(N+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(K+<span class="hljs-number">1</span>)] 
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, N+<span class="hljs-number">1</span>):  <span class="hljs-comment"># if we have only 1 egg</span>
            matrix[<span class="hljs-number">1</span>][i] = i
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">2</span>, K+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, N+<span class="hljs-number">1</span>):
                result = N
                <span class="hljs-keyword">for</span> k <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, N+<span class="hljs-number">1</span>):
                    <span class="hljs-comment"># we try to throw egg at level k</span>
                    <span class="hljs-comment">#  (1) if egg broke, then we have (i-1) egg and verify “k-1” floor,   1 + matirx[i-1][k-1]</span>
                    <span class="hljs-comment">#  (2) if egg not broke, then we have i egg and verify “j-k” floor,  1 + matrix[i][j-k] </span>
                    <span class="hljs-comment"># the result should be max of (1) and (2)</span>
                    temp = max(matrix[i<span class="hljs-number">-1</span>][k<span class="hljs-number">-1</span>], matrix[i][j-k]) + <span class="hljs-number">1</span>   
                    <span class="hljs-keyword">if</span> temp &lt; result:
                        result = temp
                matrix[i][j] = result
                <span class="hljs-comment">#print("i={0} j={1}".format(i,j))</span>
                <span class="hljs-comment">#pprint(matrix)</span>
        
        <span class="hljs-keyword">return</span> matrix[K][N]
</div></code></pre>
<h1 id="solution-2">solution 2</h1>
<ul>
<li><a href="https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/gao-lou-reng-ji-dan-jin-jie">https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/gao-lou-reng-ji-dan-jin-jie</a></li>
</ul>
<p>现在，我们稍微修改 dp 数组的定义，确定当前的鸡蛋个数和最多允许的扔鸡蛋次数，就知道能够确定 F 的最高楼层数。具体来说是这个意思：</p>
<pre><code><code><div>dp[k][m] = n
# 当前有 k 个鸡蛋，可以尝试扔 m 次鸡蛋
# 这个状态下，最坏情况下最多能确切测试一栋 n 层的楼

# 比如说 dp[1][7] = 7 表示：
# 现在有 1 个鸡蛋，允许你扔 7 次;
# 这个状态下最多给你 7 层楼，
# 使得你可以确定楼层 F 使得鸡蛋恰好摔不碎
# （一层一层线性探查嘛）


</div></code></code></pre>
<p>有递推公式</p>
<pre><code>dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1
</code></pre>
<p>第一次选择的楼层就是 dp[k-1][m-1] + 1</p>
<ul>
<li>如果鸡蛋碎了，那么剩下的下方楼层数目dp[k-1][m-1],  可以被k-1个鸡蛋, 扔m-1次覆盖</li>
<li>如果鸡蛋没碎，那么在上面的楼层数目dp[k][m-1], 也可以被k个鸡蛋， 扔m-1次覆盖</li>
</ul>
<pre><code class="language-java"><div><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">superEggDrop</span><span class="hljs-params">(<span class="hljs-keyword">int</span> K, <span class="hljs-keyword">int</span> N)</span> </span>{
    <span class="hljs-comment">// m 最多不会超过 N 次（线性扫描）</span>
    <span class="hljs-keyword">int</span>[][] dp = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[K + <span class="hljs-number">1</span>][N + <span class="hljs-number">1</span>];
    <span class="hljs-comment">// base case:</span>
    <span class="hljs-comment">// dp[0][..] = 0</span>
    <span class="hljs-comment">// dp[..][0] = 0</span>
    <span class="hljs-comment">// Java 默认初始化数组都为 0</span>
    <span class="hljs-keyword">int</span> m = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">while</span> (dp[K][m] &lt; N) {
        m++;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> k = <span class="hljs-number">1</span>; k &lt;= K; k++)
            dp[k][m] = dp[k][m - <span class="hljs-number">1</span>] + dp[k - <span class="hljs-number">1</span>][m - <span class="hljs-number">1</span>] + <span class="hljs-number">1</span>;
    }
    <span class="hljs-keyword">return</span> m;
}
</div></code></pre>
<h1 id="3-如果题目再改改-已知最大可扔次数d-楼高n-求最少需要几个鸡蛋k才能完成测试">3. 如果题目再改改。 已知最大可扔次数D, 楼高N, 求最少需要几个鸡蛋K才能完成测试？</h1>
<p>其实这样意义不大，甚至没有解， 例如我们在上面代码的基础上， 横坐标鸡蛋K, 纵坐标D可扔次数， 矩阵元素楼高。</p>
<p>列出K=10， D=4情况下，能支持的最大楼高的矩阵</p>
<pre><code><code><div>   0  1  2  3  4  5  6  7  8  9  10  
01 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
02 0, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3
03 0, 3, 6, 7, 7, 7, 7, 7, 7, 7, 7
04 0, 4, 10, 14, 15, 15, 15, 15, 15, 15, 15
05 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
</div></code></code></pre>
<p>可以看见， 所求楼高N和可扔次数D关系比较密切， 和鸡蛋数目K关系不大。</p>
<p>如果N=16, D=3, 那么无论多少个鸡蛋，都不能满足要求。</p>

    </body>
    </html>